Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-168 < prev next >

Wrap

Text File | 1988-12-01 | 33.2 KB | 827 lines

IEN: 168 VAX-UNIX Networking Support Project Implementation Description Robert F. Gurwitz Computer Systems Division Bolt Beranek and Newman, Inc. Cambridge, MA 02138 January, 1981 VAX-UNIX Networking January, 1981 Support Project IEN 168 1 Introduction The purpose of this report is to describe the implementation of network software for the VAX-11/780 * running UNIX. ** This is being done as part of the VAX-UNIX Networking Support Project. The overall purpose of this effort is to provide the capability for the VAX to communicate with other computers via packet- switching networks, such as the ARPANET. Specifically, the project centers around an implementation of the DoD standard host-host protocol, the Transmission Control Protocol (TCP) [4]. TCP allows communication with ARPANET hosts, as well as hosts on networks outside the ARPANET, by its use of the DoD standard Internet Protocol (IP) [3]. The implementation is designed for the VAX, running VM/UNIX, the modified version of UNIX 32/V developed at the University of California, Berkeley [1]. This version of UNIX includes virtual paging capabilities. In the following paragraphs, we will discuss some features and design goals of the implementation, and its organization. 2 Features of the Implementation 2.1 Protocol Dependent Features 2.1.1 Separation of Protocol Layers The TCP software that we are developing for the VAX incorporates several important features. First, the implementation provides for separation of the various protocol layers so that they can be accessed independently by various applications. (1) Thus, there is a capability for access to the TCP level, which will provide complete, reliable, multiplexed, host-host communications connections. In addition, the IP level is also accessible for applications other than TCP, which require its internet addressing and data fragmentation/reassembly services. Finally, the implementation also allows independent access to the local network interface (in this case, to the ARPANET, whose host interface is defined in BBN Report No. 1822 _______________ * VAX is a trademark of Digital Equipment Corporation. ** UNIX is a trademark of Bell Laboratories. (1) In this context, the terms application and user refer to any software that is a user of lower level networking services. Thus, programs such as FTP and TELNET can be considered applications when viewed from the TCP level, and TCP itself may be viewed as an application from the IP level. -1- VAX-UNIX Networking January, 1981 Support Project IEN 168 [2]) in a "raw" fashion, for software which wishes to communicate with hosts on the local network and do its own higher level protocol processing. 2.1.2 Protocol Functions Another feature of the implementation is to provide the full functionality of each level of protocol (TCP and IP), as described in their specifications [3,4]. Thus, on the TCP level, features such as the flow control mechanism (windows), precedence, and security levels will be supported. On the IP level, datagram fragmentation and reassembly will be supported, as well as IP option processing, gateway-host flow control (source-quenching) and routing updates. However, it is anticipated that some of these features (such as handling IP gateway-host routing updates, and IP option processing) will be implemented in later stages of development, after more basic features (such as TCP flow control and IP fragmentation/reassembly) are debugged. 2.2 Operation System Dependent Features 2.2.1 Kernel Resident Networking Software There are several features of the implementation which are operating system dependent. The most important of these is the fact that the networking software is being implemented in the UNIX kernel as a permanently resident system process, rather than a swappable user level process. This organization has several implications which bear on performance. The most obvious effect is that since the networking software is always resident, it can more efficiently respond to network and user initiated events, as it is always available to service such events and need not be swapped in. In addition, residence in the kernel removes the burden of the use of potentially inefficient interprocess communication mechanisms, such as pipes and ports, since simpler data structures, such as globally available queues, can be used to transmit data between the network and user processes. Kernel provided services, (e.g., timers and memory allocation) also become much easier and more efficient to use. -2- VAX-UNIX Networking January, 1981 Support Project IEN 168 The large address space of the VAX makes this organization practical and allows the avoidance of expedients like the NCP split kernel/user process implementation, that have been necessary in previous UNIX networking software on machines with limited address space, like the PDP 11/70. It is hoped that the kernel resident approach will contribute to the speed and efficiency of this TCP. 2.2.2 User Interface Use of the "traditional" UNIX file oriented user interface is another operating system dependent feature of this implementation. The user will access the network software by means of standard system file I/O calls: open, close, read, and write. This entails modification of certain of these calls to accommodate the extra information needed to open and maintain a connection. In addition, the communication of exceptional conditions to the user (such as the foreign host going down) must also be accommodated by extension of the standard system calls. In the case of open, for example, use of the call's mode field will be extended to accommodate a pointer to a parameter structure. In the case of exceptional conditions, the return code for reads and writes will be used to signal the presence of exceptional conditions, much like an error. An additional status call (ioctl) will be provided for the user to determine detailed information about the nature of the condition, and the general status of the connection. In this way, the necessary additional information needed to maintain network communications will be supported, while still allowing the use of the functionality that the UNIX file interface provides, such as the pipe mechanism. In the initial versions, this interface will be the standard UNIX blocking I/O mechanism. Thus, outstanding reads for data which has not been accepted from the foreign host, and writes which exceed the buffering resources of a connection will block. It is expected that the await/capacity mechanism, currently available for Version 6 systems, will be added to the VM/UNIX kernel in the near future. These non-blocking I/O modifications will be supported by the network software, relieving the blocking restriction. -3- VAX-UNIX Networking January, 1981 Support Project IEN 168 3 Design Goals Several design goals have been formulated for this implementation. Among these goals are efficiency and low operating system overhead, promoted by a kernel resident network process, which allows for reduced process and interprocess communication overhead. Another goal of the implementation is to reduce the amount of extraneous data copying in handling network traffic. To achieve this, a buffer data structure has been adopted which has the following characteristics: intermediate size (128 bytes); low overhead (10 bytes of control information per buffer); and flexibility in data handling through the use of data offset and length fields, which reduce the amount of data copying required for operations like IP fragment reassembly and TCP sequence space manipulations. The use of queueing between the various software levels has been limited in the implementation by processing incoming network data to the highest level possible as soon as possible. Thus, an unfragmented message coming from the network is passed to the IP and TCP levels, with queueing taking place at the device driver only until the message has been fully read from the network. Similarly, on the output side, data transmission is only attempted when the software is reasonably certain that the data will be accepted by the network. Finally, it is planned that the inclusion of the network software will entail relatively little modification of the basic kernel code beyond that provided by Berkeley. The only modifications to kernel code outside the network software will be slight changes to the file I/O system calls to support the user interface described above. In addition, an extension to the virtual page map data structure in low core will be necessary to support the memory allocation scheme, which makes use of the kernel's page frame allocation mechanisms. 4 Organization 4.1 Control Flow -4- VAX-UNIX Networking January, 1981 Support Project IEN 168 4.1.1 Local Network Interface The network software can be viewed as a kernel resident system process, much like the scheduler and page daemon of Berkeley VM/UNIX. This process is initiated as part of network initialization. A diagram of its control and data flow is shown in Figure 1. | |-----| |-----| |-----| |-----| | | |LOCAL| |-----| |LOCAL| | | | | | | | NET | |input| | NET | | IP | | TCP | | |->|INPUT|->|queue|->|INPUT|->|INPUT|->|INPUT| | | | I/F | |-----| | | | | | | | N | |-----|==========>|-----| |-----| |-----| | | ^ (wakeup) ^ \ (timer) | E | | | \ / | U | (input) V \ / | T | ( int ) |-----| \ / | S | |frag | |-----| |-----| | W | |queue| | |=>| |->| E | |-----| | TCP | |USER | | O | |-----||-----| |MACH | | I/F | | R | |unack|| snd |<---->| |<=| |<-| R | (outpt) |queue||queue| |-----| |-----| | | ( int ) |-----||-----| / \ / | K | | / \ / | | V / \ / | | |-----| |-----| |-----| |-----| \ / | | |LOCAL| |-----| |LOCAL| | | | | |-----| | | | NET | |outpt| | NET | | IP | | TCP | | rcv | | |<-|OUTPT|<-|queue|<-|OUTPT|<-|OUTPT|<-|OUTPT| |queue| | | | I/F | |-----| | | | | | | |-----| | | |-----|<----------|-----| |-----| |-----| | | | | | |<----------TCP PROCESS------------>| | | Figure 1 . Network Software Organization Its main flow of control is an input loop which is activated (via wakeup) by the network interface device driver when an incoming message has been completely read from the network. (It can also be awakened by TCP user or timer events, described below.) The message is then taken from an input queue and dispatched on the basis of local network format (e.g., 1822 leader link number). ARPANET imp-host messages (RFNMs, incompletes, imp/host status) -5- VAX-UNIX Networking January, 1981 Support Project IEN 168 are handled at this level. For other types of messages, the local network level input handler calls higher level "message handlers." The "standard message handler" is the IP input routine. Handlers for other protocols at this level (such as UNIX NCP) may be accommodated in either of two ways. First, a "raw message" service is available which simply queues data on specified links to/from the local network. By reading or writing on a connection opened for this service, a user process may handle its own higher level protocol communication. Alternatively, for frequently used protocols, a new handler may be defined in the kernel and called directly. 4.1.2 Internet Protocol At the IP level, the fragment reassembly algorithm is executed. Unfragmented messages with valid IP leaders are passed to the higher level protocol handler in a manner similar to the lower level dispatch, but on the basis of IP protocol number. The "standard handler" is TCP. Another protocol handler interprets IP gateway-host flow control and routing update messages. Fragmented messages are placed on a fragment reassembly queue, where incoming fragments are separated by source and destination address, protocol number, and IP identification field. For each "connection" (as defined by these fields), a linked list of fragments is maintained, tagged by fragment offset start and end byte numbers. As fragments are received, the proper list is found (or a new one is created), and the new fragment is merged in by comparing start and end byte numbers with those of fragments already on the list. Duplicate data is thrown away. A timer is associated with this queue, and incomplete messages which remain after timeout are dropped and their storage is freed. Completed messages are passed to the next level. 4.1.3 TCP Level At the TCP level, incoming datagrams are processed via calls to a "TCP machine." This is the TCP itself, which is organized as a finite state machine whose states are roughly the various states of the protocol as defined in [4], and whose inputs include incoming data from the network, user open/close/read/write requests, and timer events. Input from the network is handled directly, passing through the above described -6- VAX-UNIX Networking January, 1981 Support Project IEN 168 levels. User requests and timer events are handled through a work queue. When a user process executes a network request via system call, the relevant data (on a read or write) is copied from user to kernel space (or vice versa), a work entry is enqueued, and the network process is awakened. Similarly, when timers associated with TCP (such as the retransmission timer) go off, timer work requests are enqueued and the network input process is awakened. Once awakened, it checks for the presence of completed messages from the network interface and processes them. After these inputs are processed, the TCP machine is called to handle any outstanding requests on the work queue. The network process then sleeps, waiting for more network input or work requests. Thus, the TCP machine may be called directly with network input, or awakened indirectly to check its work queue for user and timer requests. After reset processing and sequence and acknowledgement number validation, acceptable received data is sequenced and placed on the receive queue. This sequencing process is similar to the IP fragment reassembly algorithm described above. Data placed on this queue is acknowledged to the foreign host. Received data whose sequence numbers lie outside the current receive window are not processed, but are placed on an unacknowledged message queue. The advertised receive window is determined on the basis of the remaining amount of buffering allocated to the connection (see below). When buffering becomes available, data on the unacknowledged message queue is then processed and placed on the receive data queue. On the output side, TCP requests for data transmission result in calls to the IP level output routine. This routine does fragmentation, if necessary, and makes calls on the local network output routine. Outgoing messages are then placed on a buffering queue, for transmission to the network interface by the device driver. In data transmission, an attempt is made to ensure that data moving from the highest level (TCP), will not be sent unless there is reasonable certainty that the lower levels will have the necessary resources to accept the message for transmission to the network. All data to be sent is maintained on a single send queue, where data is added on user writes, and removed when proper acknowledgement is received. Whenever the TCP machine sends data, a retransmission timer is set, and the sequence number of the first data byte on the queue is saved. After initial transmission the sequence number of the next data to send is advanced beyond what was first sent. If the retransmission timer -7- VAX-UNIX Networking January, 1981 Support Project IEN 168 goes off before that data is acknowledged, the sequence number of the next data to send is backed up, and the contents of the send buffer (for the length determined by the current send window) is retransmitted, with the ACK and window fields set appropriately. The retransmission timer is set with increasingly higher values from 3 to 30 seconds, if the saved sequence number does not advance. A persistence timer is also set when data is sent. This allows communication to be maintained if the foreign process advertises a zero length window. When the persistence timer goes off, one byte of data is forced out of the TCP. 4.2 Buffering Strategy As mentioned earlier, all data is passed from the network to the various protocol software layers in intermediate sized (128 byte) buffers. The buffers have two chain pointers, a data offset, and a data length field (see Figure 2). As data is read from the network or copied from the user, multiple buffers are chained together. Protocol headers are also held in these buffers. As messages are passed between the various software levels, the offset is modified to point at the appropriate header. The length field gives the end of data in a particular buffer. This offset/length pair facilitates merging of messages in IP fragment reassembly and TCP sequencing. The allocation of these buffers is handled by the network software. Buffers are obtained by "stealing" page frames from the kernel's free memory map (CMAP). In VM/UNIX, these page frames are 1024 bytes long, and thus have room for eight 128 byte buffers. The advantage of using kernel paging memory as a source of network buffers is that their allocation can be done totally dynamically, with little effect on the operation of the overall system. Buffers are allocated from a cache of free page frames, maintained on a circular free list by the network memory allocator. As the demand for buffers increases, new page frames are stolen from the paging freelist and added to the network buffer cache. Similarly, as the need for pages decrease, free pages are returned to the system. To minimize fragmentation in buffer allocation within the page frames, the free list is sorted. When no more pages are available for allocation, data on the IP reassembly and TCP unacknowledged data queues are dropped, and their buffers are recycled. -8- VAX-UNIX Networking January, 1981 Support Project IEN 168 ^ |------------------------| ^ | | -> NEXT BUFFER | | 10 |------------------------| | BYTES | QUEUE LINK | | | |-----------|------------| | V | OFFSET | LENGTH | | |-----------|------------| | | | 128 | | BYTES | | | | D A T A | | | | | | | | | | | | | | |------------------------| V Figure 2 . Layout of a Network Buffer The number of pages that can be stolen from the system is limited to a moderate number (in practice 64-256, depending on network utilization in a particular system). To enforce fairness of network resource utilization between connections, the number of buffers that can be dedicated to a particular connection at any time is limited. This limit can be varied to some small degree by the user when a connection is opened. Thus, a TELNET user may open a connection with the minimum 1K bytes of send and receive buffering; while an FTP user, anticipating larger transfers, might desire up to 4K of buffering. The effect of this connection buffering allocation is to place a limit on the amount of data that the TCP may accept from the user for sending before blocking, and the amount of input from the network that the TCP may acknowledge. Note that in receiving, the network software may allocate available buffers beyond the user's connection limit for incoming data. However, this data is considered volatile, and may be dropped when buffer demands go higher. Incoming data is acknowledged by TCP only until the user's connection buffer limit is exhausted. The advertised TCP flow control window for a connection is set on the basis of the remaining amount of this buffering. Thus, the network software must insure that it has enough buffering for 1) its own internal use in processing data on the IP and local network levels; 2) retaining acknowledged TCP data -9- VAX-UNIX Networking January, 1981 Support Project IEN 168 that have not been copied to user space; and 3) retaining data accepted by the TCP for transmission which have not yet been acknowledged by the foreign host TCP. Other data, such as unacknowledged TCP input from the network and fragments on the IP reassembly queue are vulnerable to being dropped when demand for more buffers makes necessary the recycling of buffers on these queues. Since there is an absolute limit on the number of page frames that may be stolen from the paging system, and hence the total number of buffers available, there is a resultant limit on the total number of simultaneous connections. Several data structures are required for stealing page frames from the kernel and maintaining the buffer free list. These include enough page table entries for mapping the maximum number of page frames which can be stolen from the system, an allocation map for allocating these page table entries, and the free page list itself. For a 256 page maximum, this requires 2K bytes of page tables, 1K bytes for page frame allocation mapping, and another 1K bytes for the network freelist. The maximum page parameter and others, including the minimum and maximum amount of buffering that the user may specify are modifiable constants of the implementation. 4.3 Data Structures Along with the data structures needed to support the buffer management system, there are several others used in the network software (see Figure 3). The focus of activity is the user connection block (UCB), and the TCP control block (TCB). The UCB is allocated from a table on a per connection basis. It holds non-protocol specific information to maintain a connection. This includes a pointer the UNIX process structure of the opener of a connection, (2) a pointer to the foreign host entry for the peer process's host, a pointer to the protocol-specific connection control block (for TCP, the TCB), pointers to the user's send and receive data buffer chain, and miscellaneous flags and status information. When a network connection is opened, an entry in the user's open file table is allocated, which holds a pointer to the UCB. For TCP connections, a TCB is allocated. All TCBs are chained together to facilitate buffer recycling. The TCB contains a pointer to the corresponding UCB, a block of sequence number variables and state flags used by the TCP finite state _______________ (2) For details on data structures specific to UNIX, see [5]. -10- VAX-UNIX Networking January, 1981 Support Project IEN 168 Foreign Host Table |--------| Network |------>|Host Adr| Conn Table | |--------| |--------| | | #RFNM | |--->|->Proc |<--+--| |--------| | |--------| | | | Status | | |->Host |---| | |--------| Per User | |--------| | File Table | | ->TCB |---| | TCB |--------| | |--------| | | |--------| | Flags | | |->S Buf | |--+--->| ->next | |--------| | |--------| | |--------| | ->UCB |---| |->R Buf | |----| ->UCB | |--------| |--------| |--------| | Flags | | FSM | | and | |Sequence| | Status | | Vars | |--------| |--------| |->Snd Q | |--------| |->Rcv Q | |--------| |->UnackQ| |--------| | Flags | | and | | Status | |--------| Figure 3 . Network Data Structures machine, pointers to the various TCP data queues, and flags and state variables. Protocols other than TCP would have their own control blocks instead of the TCB. For the "raw" local network and IP handlers, all necessary information is kept in the UCB. Finally, there is a foreign host table, where entries are allocated for each host that is part of a connection. The entry contains the foreign host's internet address, the number of outstanding RFNM's for 1822 level host-imp communication, and the status of the foreign host. Entries in this table are hashed on the foreign host address. -11- VAX-UNIX Networking January, 1981 Support Project IEN 168 5 References [1] Babaoglu, O., W. Joy, and J. Porcar, "Design and Implementation of the Berkeley Virtual Memory Extensions to the UNIX Operating System," Computer Science Division, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, December, 1979. [2] Bolt Beranek and Newman, "Specification for the Interconnection of a Host and an IMP," Bolt Beranek and Newman Inc., Report No. 1822, May 1978 (Revised). [3] Postel, J. (ed.), "DoD Standard Internet Protocol," Defense Advanced Research Projects Agency, Information Processing Techniques Office, RFC 760, IEN 128, January, 1980. [4] Postel, J. (ed.), "DoD Standard Transmission Control Protocol," Defense Advanced Research Projects Agency, Information Processing Techniques Office, RFC 761, IEN 129, January, 1980. [5] Thompson, K., "UNIX Implementation," The Bell System Technical Journal, 57 (6), July-August, 1978, pp. 1931-1946. -12- VAX-UNIX Networking January, 1981 Support Project IEN 168 Table of Contents 1 Introduction.......................................... 1 2 Features of the Implementation........................ 1 2.1 Protocol Dependent Features......................... 1 2.1.1 Separation of Protocol Layers..................... 1 2.1.2 Protocol Functions................................ 2 2.2 Operation System Dependent Features................. 2 2.2.1 Kernel Resident Networking Software............... 2 2.2.2 User Interface.................................... 3 3 Design Goals.......................................... 4 4 Organization.......................................... 4 4.1 Control Flow........................................ 4 4.1.1 Local Network Interface........................... 5 4.1.2 Internet Protocol................................. 6 4.1.3 TCP Level......................................... 6 4.2 Buffering Strategy.................................. 8 4.3 Data Structures.................................... 10 5 References........................................... 12 -i-